package main.Q801_900;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Q801_810 {
	public static void main(String[] args) {
		System.out.println("Question801：");
		System.out.println("Question802：找到最终的安全状态");
		System.out.println("Question803：");
		System.out.println("Question804：唯一摩尔斯密码词");
		System.out.println("Question805：");
		System.out.println("Question806：");
		System.out.println("Question807：保持城市天际线");
		System.out.println("Question808：");
		System.out.println("Question809：");
		System.out.println("Question810：");
	}
}

class Question802 {
	public List<Integer> eventualSafeNodes(int[][] graph) {
		int n = graph.length;
		int[] color = new int[n];
		List<Integer> ans = new ArrayList<Integer>();
		for (int i = 0; i < n; ++i) {
			if (process(graph, color, i)) ans.add(i);
		}
		return ans;
	}

	public boolean process(int[][] graph, int[] color, int x) {
		if (color[x] > 0) return color[x] == 2;
		color[x] = 1;
		for (int y : graph[x]) {
			if (!process(graph, color, y)) return false;
		}
		color[x] = 2;
		return true;
	}
}

class Question804 {
	public int uniqueMorseRepresentations(String[] words) {
		String[] code = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.",
				"....", "..", ".---", "-.-", ".-..", "--", "-.",
				"---", ".--.", "--.-", ".-.", "...", "-", "..-",
				"...-", ".--", "-..-", "-.--", "--.."};
		Set<String> set = new HashSet<>();
		for (String word : words) {
			char[] chars = word.toCharArray();
			StringBuffer str = new StringBuffer();
			for (char c : chars) {
				str.append(code[c - 'a']);
			}
			set.add(str.toString());
		}
		return set.size();
	}
}

class Question807 {
	public int maxIncreaseKeepingSkyline(int[][] grid) {
		int result = 0;
		int[][] maxHeight = new int[2][grid.length];
		for (int i = 0; i < grid.length; i++) {//行最高
			int max = grid[i][0];
			for (int j = 0; j < grid[0].length; j++) {
				max = Math.max(max, grid[i][j]);
			}
			maxHeight[0][i] = max;
		}
		for (int i = 0; i < grid.length; i++) {//列最高
			int max = grid[0][i];
			for (int j = 0; j < grid[0].length; j++) {
				max = Math.max(max, grid[j][i]);
			}
			maxHeight[1][i] = max;
		}
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid.length; j++) {
				int min = Math.min(maxHeight[0][i], maxHeight[1][j]);
				if (min > grid[i][j]) result += min - grid[i][j];
			}
		}
		return result;
	}
}